import collections
from typing import List


class Solution:
    def countSteppingNumbers(self, low: int, high: int) -> List[int]:
        ans = []
        if low == 0:
            ans.append(0)

        queue = collections.deque([i for i in range(1, 10)])
        while queue:
            now = queue.popleft()
            if now > high:
                return ans
            if now >= low:
                ans.append(now)
            last_bit = now % 10
            if last_bit > 0:
                queue.append(now * 10 + (last_bit - 1))
            if last_bit < 9:
                queue.append(now * 10 + (last_bit + 1))


if __name__ == "__main__":
    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21]
    print(Solution().countSteppingNumbers(low=0, high=21))
